/**
 * 23. 合并K个升序链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */

const { displayListNode, createListNode } = require('../../libs/public');

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function merge(list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  let head1 = list1;
  let head2 = list2;
  let head;
  if (head1.val < head2.val) {
    head = head1;
    head1 = head1.next;
  } else {
    head = head2;
    head2 = head2.next;
  }
  let cur = head;
  while (head1 && head2) {
    if (head1.val < head2.val) {
      cur.next = head1;
      head1 = head1.next;
    } else {
      cur.next = head2;
      head2 = head2.next;
    }
    cur = cur.next;
  }
  let left = head1 || head2;
  while (left) {
    cur.next = left;
    left = left.next;
    cur = cur.next;
  }
  return head;
}

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
function mergeKLists(lists) {
  const kCount = lists.length;
  if (!kCount) return null;
  let head = lists[0];
  for (let i = 1; i < kCount; i += 1) {
    head = merge(head, lists[i]);
  }
  return head;
}

console.log(displayListNode(mergeKLists([])) === '[]');
console.log(displayListNode(mergeKLists([
  createListNode([]),
])) === '[]');
console.log(displayListNode(mergeKLists([
  createListNode([1, 4, 5]),
  createListNode([1, 3, 4]),
  createListNode([2, 6]),
])) === '[1,1,2,3,4,4,5,6]');
